The present invention relates to radio frequency identification (RFID).
Radio frequency identification (RFID) is a method to retrieve and store data using a radio channel. A RFID system consists of tags and a reader. A tag typically consists of radio-frequency circuits, a CPU, and a small memory and has a unique identifier, or “TAG_ID.” By means of wireless communication between a reader and tags in which the tags identify themselves by communicating their respective identifiers to the reader, RFID systems track and/or manage objects in real-time.
One of the most challenging issues in RFID systems is the tag collision problem. When only one RF channel is used, as is typically the case in passive RFID systems, it is impossible to avoid collisions during communication between a reader and multiple tags. Passive tags only listen and respond to requests from the reader and do not interact with one another.
Several collision resolution protocols have been proposed for RFID systems. These protocols use similar principles but perform differently under different situations.
For example, the binary tree protocol—described, for example, in J. Capetanakis, “Tree algorithms for packet broadcast channels,” IEEE Transaction on Information Theory, IT-25(5):505-515, September 1979; K. Finkenzeller, RFID Handbook, John Wiley & Sons, New York, 1999; and J. L. Massey “Collision-resolution algorithms and random-access communications,” Multiuser Communication Systems, ed. G. Longo (Spriger, New York, 1981) 73-137.—repetitively divides the colliding tags into two groups until only one tag remains. The binary tree protocol can be implemented using either of two approaches: a deterministic one or a probabilistic one. The deterministic protocol divides the tag population using the TAG_IDs, while the probabilistic protocol divides the tag population by having tags choose 0 or 1 uniformly randomly. The RFID standard, “EPC Class 1 Generation 1” is based on the binary tree protocol and employs 8 bin slots to reduce collision probability among tags, as described, for example, in “EPC radio frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860-960 MHz,” EPCglobal Inc., Technical Report, 2004. Here, tags determine their own bin slot using their TAG_ID and can only access their own bin slot. If only one tag hits the specific bin slot, the tag is identified. However, selection of the appropriate number of bin slots is a challenging problem. As the number of bin slots gets smaller relative to the tag population, the collision-spreading effect of this approach becomes less effective. On the other hand, if the number of bin slots is far bigger than the tag population, the bin slot hit ratio decreases, causing more delay. Thus this protocol has to estimate the tag population in order to choose the optimal number of bin slots.
Tree slotted ALOHA—such as described in M. A. Bonuccelli, F. Lonetti, and F. Martelli, “Tree slotted aloha: a new protocol for tag identification in RFID networks,” Proceedings of the 2006 International Symposium on World of Wireless, Mobile and Multimedia Networks, pages 603-608, 2006—and the Adaptive Binary Splitting (ABS) protocol—such as described in J. Myung and W. Lee, “Adaptive binary splitting: a RFID tag collision arbitration protocol for tag identification,” Mobile Networks and Applications, 11 (5):711-722, 2006—combine the collision-spreading technique and the time slot allocation to improve the collision resolution performance. The ABS protocol takes account of tag mobility. In this protocol, unknown tags choose a time slot number between 0 and a maximum slot number that is previously determined. This approach intentionally generates collisions between previously identified, or “known,” tags and not-previously-identified, or “known,” tags that have just arrived in the reader's interrogation zone to trigger the binary tree collision resolution. However, intentionally generated collisions introduce communication overhead in that the reader conducts the identification procedure for both the “known” and “newly” arrived tags.
Many prior tag identification protocols, including several of the protocols cited above, improve performance parameters such as speed of identification and the number of iterations required to identify the tags. However, many of those protocols are designed to identify all the tags from scratch whenever the reader performs identification rather than identifying only changes in the tag population that resulted from tag mobility, i.e., tags moving into or out of the reader's interrogation zone. There are a few protocols that consider tag mobility, but they still have an overhead problem that needs to be eliminated for better performance.